package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.regex.Pattern;

import org.apache.commons.collections15.BidiMap;
import org.apache.commons.collections15.bidimap.DualHashBidiMap;

import edu.siu.math.egut.local.SectionIntegral.UnipotentPrefixPair;
import edu.siu.math.egut.main.OutputStyle;

/**
 * The Class Unipotent models certain unipotent elements of split connected
 * reductive algebraic groups. Let G be such a group and assume that G is
 * equipped with a choice of maximal torus T, used to define roots. Let U be a
 * maximal unipotent subgroup of G which is compatible with T. Any element of U
 * can be written as a product of elements of the form x_a(r) where, for a root
 * a, x_a is an isomorphism between the one-dimensional unipotent subgroup
 * associated to a and the additive group-scheme. Such elements are called
 * "simple unipotents," or sunipotents for short. A unipotent is represented
 * simply as a product of sunipotents. Because not every word in the sunipotents
 * corresponds to a unipotent element of G, it is possible to define objects of
 * class Unipotent which are not, actually, unipotent. Some checking is done to
 * guard against this, but a certain amount of care and/or exception-handling on
 * the users part will be required.
 * 
 * 
 * @author Joe Pleso
 * @author Joseph Hundley
 * 
 */
public class Unipotent implements Serializable {

    /**
     * In symbolically manipulating unipotent elements, one often wants to
     * introduce variables indexed by the roots of some T-stable unipotent
     * subgroup. These variables are then determined by an initial String prefix
     * and a root.
     * 
     * @author Joseph Hundley
     * 
     */
    public static class PrefixRootPair {
	private final String prefix;
	private final int[] root;

	/**
	 * @return the prefix to the pair
	 */
	public String getPrefix() {
	    return prefix;
	}

	/**
	 * @param prefix
	 *            the desired prefix
	 * @param root
	 *            the desired root
	 */
	public PrefixRootPair(final String prefix, final int[] root) {
	    super();

	    this.prefix = prefix;
	    this.root = root;
	}

	/**
	 * @return the root from the pair
	 */
	public int[] getRoot() {
	    return root;
	}

    }

    /**
     * @author Joseph Hundley
     * 
     */
    public enum InputStyle {
	/**
	 * The "style" for any input which can not be parsed.
	 */
	NONSENSE,
	/**
	 * An input style for inputing unipotent elements: a list of roots
	 * followed by a string "prefix."
	 */
	ROOTS_PLUS_STRING

    }

    private static final long serialVersionUID = 517L;
    // private static final char[] DROP_ROOT_MENU_OPTIONS = { 'K', 'k', 'S',
    // 's',
    // 'C', 'c' };
    private static final Pattern ROOTS_PLUS_STRING_PATTERN = Pattern
	    .compile(
		    "unipotent\\s*roots\\s*\\[\\s*(\\[(\\d,\\s*)*\\d\\s*\\],?\\s*)*\\]\\s*prefix.*",
		    Pattern.CASE_INSENSITIVE);
    /**
     * The pattern matched by "default" variables. (E.g., those created by the
     * int[][], String Constructor.)
     */
    public static final Pattern DEFAULT_VARIABLE_PATTERN = Pattern
	    .compile(".*_\\{-?\\d\\d+\\}");
    private static final int PAGE_WIDTH = edu.siu.math.egut.io.Constants.PAGE_WIDTH;

    /**
     * Multiply two Unipotents together. The Unipotents must be from the same
     * group.
     * 
     * @param a
     *            the first Unipotent to be multiplied
     * @param b
     *            the second Unipotent to be multiplied
     * @return the product ab of Unipotents a and b, with all associations of a
     *         preserved, and associations of b preserved iff they are
     *         consistent with those of a.
     * 
     */
    /*
     * WARNING: This method will create Unis in which all Sunis are immobile.
     */

    public static Unipotent multiply(Unipotent a, Unipotent b) {
	if (a.getGroup() != b.getGroup()) {
	    throw new IllegalArgumentException();
	}

	List<Sunipotent> list = new ArrayList<Sunipotent>();
	list.addAll(a.product);
	list.addAll(b.product);

	Unipotent c = new Unipotent(a.getGroup(), list);
	for (Sunipotent s : a.associations.keySet()) {
	    c.associate(s, a.associations.get(s));
	}
	for (Sunipotent s : b.associations.keySet()) {
	    if (!c.associations.containsValue(b.associations.get(s)))
		c.associate(s, b.associations.get(s));
	}

	return c;

    }

    /**
     * Multiply a Unipotent by a Sunipotent (on the right). The Unipotents must
     * be from the same root system.
     * 
     * @param u
     *            Unipotent
     * @param s
     *            Sunipotent
     * @return the product u.s of u and s, as a Unipotent object with all
     *         associations of u preserved, no association assigned to s.
     * 
     */
    /*
     * WARNING: This method will create Unis in which all Sunis are immobile.
     */

    public static Unipotent times(Unipotent u, Sunipotent s) {
	if (u.getGroup().getRank() != s.getRoot().length) {
	    throw new IllegalArgumentException();
	}

	List<Sunipotent> list = new ArrayList<Sunipotent>();
	list.addAll(u.product);
	list.add(s);

	Unipotent c = new Unipotent(u.getGroup(), list);
	for (Sunipotent s1 : u.associations.keySet()) {
	    c.associate(s1, u.associations.get(s1));
	}

	return c;

    }

    /**
     * Modify the current Unipotent by appending the given Sunipotent to it.
     * 
     * @param s
     *            a Sunipotent
     */
    public void rightMultiply(Sunipotent s) {
	if (s.getRoot().length != this.group.getRank()) {
	    throw new IllegalArgumentException();
	}

	product.add(s);

    }

    /**
     * Modify the current Unipotent by appending the given Sunipotent to it.
     * 
     * @param s
     *            a Sunipotent
     */
    public void leftMultiply(Sunipotent s) {
	if (s.getRoot().length != this.group.getRank()) {
	    throw new IllegalArgumentException();
	}

	product.add(0, s);

    }

    /**
     * Conjugates the unipotent by a word in the standard representatives for
     * the simple reflections in the Weyl group.
     * 
     * @param weylAsInt
     *            an integer, interpreted as a word in the simple reflections,
     *            with each digit being an individual reflection. An error will
     *            result if any of the digits exceeds the rank of the ambient
     *            group.
     */
    public void actBy(int weylAsInt) {

	for (int i = 0; i < product.size(); i++) {
	    Sunipotent newSuni = get(i).imageUnder(weylAsInt);
	    if (isMobile(i)) {
		immobile.remove(get(i));
		immobile.add(newSuni);
	    }
	    if (stringOf(get(i)) != null) {
		associate(newSuni, stringOf(get(i)));
	    }
	    product.remove(i);
	    product.add(i, newSuni);

	}

    }

    private final List<Sunipotent> product;
    private final Group group;
    private boolean done;

    private final List<Sunipotent> immobile;
    // Used in simplification of unipotents. When two
    // Unipotents with the same root must be combined, this is
    // used to determine how and where.

    /*
     * FIXME note that a given Sunipotent could appear more than once in the
     * product. In the current implementation, a Sunipotent must be either
     * mobile or immobile, and since that status is attached to the Sunipotent
     * itself it applies to every occurrence. This may be unwanted in rare
     * circumstances.
     */
    private BidiMap<Sunipotent, String> associations;

    // Allows the user to associate particular variables
    // to particular Sunipotents and vice versa.

    /**
     * Create a Unipotent that has the form x_{alpha_1}(s1) x_{alpha_2}(s2)...
     * 
     * @param g
     *            the Group in which the unipotent lives
     * @param roots
     *            a list of roots
     * @param s
     *            a string prefix that will have numbers appended to it
     * @throws NotARootException
     *             if any row of roots is not a root of g.
     */
    public Unipotent(Group g, int[][] roots, String s) throws NotARootException {
	group = g;
	List<Sunipotent> list = new ArrayList<Sunipotent>();
	BidiMap<Sunipotent, String> map = new DualHashBidiMap<Sunipotent, String>();
	for (int i = 0; i < roots.length; i++) {
	    String si = defaultString(s, roots[i]);
	    Sunipotent x;
	    x = Sunipotent.create(roots[i], Polynomial.create(si));
	    list.add(x);
	    map.put(x, si);

	}
	product = list;
	immobile = new ArrayList<Sunipotent>(list);
	// all Sunipotents are immobile
	associations = map;
	// every Sunipotent owns the variable with which it is initialized.
    }

    /**
     * This method constructs a "default variable" given a string and a root.
     * The idea is that on a large unipotent one might want the variables to be
     * u_{\alpha_1} \dots u_{\alpha_r}, indexed by the root in the unipotent,
     * which then appear as subscripts.
     * 
     * 
     * @param s
     *            a string
     * @param is
     *            a tuple which should represent a root
     * @return a String representation of s subscripted with is
     */
    public final static String defaultString(String s, int[] is) {
	return s + "_{" + rootToShortString(is) + "}";
    }

    /**
     * Returns a String representation of the tuple which will be short and
     * easily readable, provided that the tuple satisfies two properties of
     * roots: (1) all entries are either nonpositive or nonnegative, (2) no
     * entry exceeds 9. This method will not check these properties, much less
     * check that the parameter is actually a root of some exceptional group.
     * However, if either property fails, the String returned may not look much
     * like a short representation of the tuple.
     * 
     * @param root
     *            should be either "positive" (no negative entries) of
     *            "negative" (no positive entries)
     * @return concatenation of all entries if positive, concatenation of
     *         absolute values, with a single "-" at the beginning, if negative.
     */
    public final static String rootToShortString(int[] root) {
	int sign = 1;
	StringBuffer sb = new StringBuffer();
	for (int i = 0; i < root.length; i++) {
	    if (root[i] < 0)
		sign = -1;
	    sb.append((root[i] * sign));
	}
	return ((sign == -1) ? "-" : "") + sb.toString();

    }

    /**
     * Creates a new Unipotent with the specified parameters.
     * 
     * @param g
     *            the group in which this Unipotent lives
     * @param l
     *            the list of Sunipotent factors
     */
    public Unipotent(Group g, List<Sunipotent> l) {
	if (g == null)
	    throw new NullPointerException();

	group = g;
	product = new ArrayList<Sunipotent>(l);
	immobile = new ArrayList<Sunipotent>(l);
	// by default all Sunipotents are immobile
	associations = new DualHashBidiMap<Sunipotent, String>();
	// no associations are created

    }

    /**
     * Constructor which constructs a unipotent from an int[][], which is
     * interpreted as a list of roots, and a String.
     * 
     * For example if passed the int[][] {{1,1},{2,1},{3,1},{3,2}} and the
     * String "u", this method creates a Unipotent
     * 
     * x_{[1,1]}(u11) x_{[2,1]}(u21) ... x_{[3,2]} (u32).
     * 
     * In general, for each root on the list, a Sunipotent is created which has
     * the specified root and an argument which is a simple polynomial
     * consisting of a single (String) variable raised to the first power. This
     * variable is obtained by appending a short string representation of the
     * root to the end of the String argument of this method, which is thus a
     * kind of "default variable prefix."
     * 
     * All terms are immobile, each Sunipotent is then associated to the
     * (unique) variable in its argument.
     * 
     * NOTE 1: If a root appears more than once on our list, then it will
     * produce the same Sunipotent each time that it appears. (By definition, a
     * Sunipotent is completely determined by its root and argument, so one
     * would not speak of two Sunipotents with the same root and argument, but
     * of the same Sunipotent appearing twice in a product.)
     * 
     * NOTE 2: if an int[][] containing int[]'s which are not roots is passed,
     * the error will not be detected by this Constructor.
     * 
     * @param roots
     *            an int[][], which will be interpreted as a list of roots
     * @param s
     *            a String, which will be the "prefix" on all the variables.
     * @throws NotARootException
     *             if the int[][] passed does not consist of roots
     */
    public Unipotent(final int[][] roots, final String s)
	    throws NotARootException {

	group = Group.getGroup(roots[0].length);

	// create a list of Sunipotents
	List<Sunipotent> list = new ArrayList<Sunipotent>();

	// create a Bidi map for associations
	BidiMap<Sunipotent, String> map = new DualHashBidiMap<Sunipotent, String>();

	// for each root on the list.
	for (int i = 0; i < roots.length; i++) {
	    /*
	     * we make a Sunipotent. The first step is to build the variable
	     * associated to our root.
	     * 
	     * Begin with the String s, add a short string representation of the
	     * root.
	     */
	    String si = defaultString(s, roots[i]);

	    /*
	     * Now form a Sunipotent whose root is our root and whose argument
	     * is the variable we just built, regarded as a very simple
	     * Polynomial.
	     */
	    Sunipotent x;
	    x = Sunipotent.create(roots[i], Polynomial.create(si));

	    // add the Sunipotent to the product
	    list.add(x);
	    // add the pair to the map.
	    map.put(x, si);

	}

	product = list;
	immobile = new ArrayList<Sunipotent>(list);
	// all Sunipotents are immobile
	associations = map;
	// every Sunipotent owns the variable with which it is initialized.
    }

    /*
     * Our preferred constructors throw NotARootExceptions. It is necessary to
     * have a simple, safe constructor which does not throw checked exceptions
     * so that one can assure that variables are always initialized.
     */

    /**
     * No argument Constructor. Initializes everything to null.
     */
    public Unipotent() {
	group = null;
	immobile = null;
	product = null;
    }

    /**
     * Constructor. Instantiates the identity element (empty product) of the
     * Group of the specified rank.
     * 
     * @param rank
     *            the int representing the semisimple rank of the grouip
     */
    public Unipotent(final int rank) {
	group = Group.getGroup(rank);
	immobile = new ArrayList<Sunipotent>();
	product = new ArrayList<Sunipotent>();
    }

    /**
     * Default Constructor
     * 
     * @param product2
     *            terms of desired product
     * @param group2
     *            desired group
     * @param immobile2
     *            indicates which terms are "immobile" (for simplification
     *            algorithms.)
     * @param associations2
     *            desired list of associations (for change of variable
     *            algorithms.)
     */
    public Unipotent(List<Sunipotent> product2, Group group2,
	    List<Sunipotent> immobile2,
	    BidiMap<Sunipotent, String> associations2) {
	product = new ArrayList<Sunipotent>(product2);
	group = group2;
	immobile = new ArrayList<Sunipotent>(immobile2);
	associations = new DualHashBidiMap<Sunipotent, String>(associations2);
    }

    /**
     * Creates a new association between a given Sunipotent and a given string
     * 
     * 
     * @param suni
     *            Sunipotent the sunipotent for the new association
     * @param s
     *            String the string for the new association
     */
    public void associate(Sunipotent suni, String s) {
	if (suni != null && s != null)
	    associations.put(suni, s);
    }

    /**
     * Removes an association
     * 
     * @param suni
     *            the sunipotent to be disassociated
     */
    public void disassociate(Sunipotent suni) {
	associations.remove(suni);

    }

    /**
     * Removes an association
     * 
     * @param s
     *            the String to be disassociated
     */
    public void disassociate(String s) {
	associations.removeValue(s);

    }

    /**
     * @return the list of (Sunipotent) terms of a Unipotent.
     */
    public List<Sunipotent> getTerms() {
	return product;
    }

    /**
     * Inserts the new Sunipotent at the given location.
     * 
     * @param location
     *            index in which to insert the new Sunipotent
     * @param newSuni
     *            the Sunipotent to be inserted
     */
    public void add(int location, Sunipotent newSuni) {
	product.add(location, newSuni);
    }

    /**
     * Attempts to shuffle sunipotents around and combine terms with the same
     * root.
     * 
     * 
     */

    public void cleanUp() {
	/*
	 * TODO implement a "smart" cleanUp which begins by computing the
	 * "depth function" determined by the unipotent (or throwing a
	 * nonUnipotentException if unable to) and then decides which "fixes" to
	 * perform based on depth.
	 */

	done = false;
	while (!done) {
	    done = true;
	    preFix();
	}

    }

    private void fix(int i, int j) {

	// We need to move the sunipotents at indices i,j together
	// we need logic to determine whether we push the one
	// on the right left or the one on the left right

	done = false;

	if (isMobile(i)) {

	    combineRight(i, j);

	} else {// this means j is mobile

	    combineLeft(i, j);
	}

    }

    /**
     * Combines two Sunipotents with the same root at the position currently
     * occupied by the one on the left.
     * 
     * If s1 = x_a(p) and s2 = x_a(q), then s1*s2 = x_a(p+q). In order to
     * simplify unipotents, we seek out pairs of Sunipotents with the same root
     * and try to combine them. If the two are not currently adjacent, this
     * process with involve commutation relations with any intervening terms.
     * 
     * E.G. s1 s3 s4 s2 = s1 s2 (s2^{-1}, s3) s3 (s2^{-1}, s4) s4
     * 
     * @param i
     *            integer, should satisfy -1 < i < j
     * @param j
     *            integer, should satisfy i < j < product.size
     * 
     *            The new sunipotent produced by combining them will inherit any
     *            associations of s1 and s2. In the case when s1 and s2 both
     *            have associated strings, the string of s1 is inherited.
     * 
     */
    public void combineLeft(final int i, final int j) {
	// check that the combination is valid
	if (!(Arrays.equals(product.get(i).getRoot(), product.get(j).getRoot()) && (i < j)))
	    throw new RuntimeException();

	// check that i is to the left of j.
	if (i > j)
	    combineLeft(j, i);

	// formula: a b c = a c c^{-1} b c b^{-1} b = ac (c^{-1},b) b
	// whence: a b c ... e = ae (e^{-1}, b) b (e^{-1}, c) c ...

	Sunipotent sinv = Sunipotent.create(product.get(j).getRoot(), product
		.get(j).getArgument().times(-1));
	Polynomial newArg = product.get(j).getArgument().plus(
		product.get(i).getArgument());
	Sunipotent newTerm = Sunipotent
		.create(product.get(j).getRoot(), newArg);
	if (!(isMobile(i) && isMobile(j)) && newArg != Polynomial.create(0))
	    immobile.add(newTerm);
	immobile.remove(get(i));
	immobile.remove(get(j));
	if (stringOf(get(j)) != null)
	    associate(newTerm, stringOf(get(j)));
	if (stringOf(get(i)) != null)
	    associate(newTerm, stringOf(get(i)));
	product.remove(j);
	for (int k = j - 1; k > i; k--) {
	    product.addAll(k, group.commutator(sinv, product.get(k)));
	}
	product.remove(i);
	if (newArg != Polynomial.create(0))
	    product.add(i, newTerm);

    }

    /**
     * Combines two Sunipotents with the same root at the position currently
     * occupied by the one on the right.
     * 
     * If s1 = x_a(p) and s2 = x_a(q), then s1*s2 = x_a(p+q). In order to
     * simplify unipotents, we seek out pairs of Sunipotents with the same root
     * and try to combine them. If the two are not currently adjacent, this
     * process with involve commutation relations with any intervening terms.
     * 
     * E.G. s1 s3 s4 s2 = (s1,s3) s3 (s1,s4) s4 s1 s2
     * 
     * The new term will inherit any associations of s1 and s2. If both s1 and
     * s2 participate in associations, then the new term will end up with the
     * association of s2.
     * 
     * @param i
     *            integer, should satisfy -1 < i < j
     * @param j
     *            integer, should satisfy i < j < product.size
     */
    public void combineRight(final int i, final int j) {
	// check that the combination is valid
	if (!(Arrays.equals(product.get(i).getRoot(), product.get(j).getRoot()) && i < j))
	    throw new RuntimeException();

	// formula a b c = a b a^{-1} b^{-1} b a c = (a,b) b ac
	// whence: a b c ... e = (a,b) b (a,c) c ... ae.
	Sunipotent s = product.get(i);
	Polynomial newArg = product.get(j).getArgument().plus(
		product.get(i).getArgument());
	Sunipotent newTerm = Sunipotent
		.create(product.get(j).getRoot(), newArg);
	if (!(isMobile(i) && isMobile(j)) && newArg != Polynomial.create(0))
	    immobile.add(newTerm);
	immobile.remove(get(i));
	immobile.remove(get(j));
	if (stringOf(get(i)) != null)
	    associate(newTerm, stringOf(get(i)));
	if (stringOf(get(j)) != null)
	    associate(newTerm, stringOf(get(j)));
	product.remove(j);
	if (newArg != Polynomial.create(0))
	    product.add(j, newTerm);
	for (int k = j - 1; k > i; k--) {
	    product.addAll(k, group.commutator(s, product.get(k)));
	}
	product.remove(i);
    }

    /**
     * Returns the Sunipotent at the specified position in the product.
     * 
     * @param index
     *            the index of the term to be retrieved
     * @return the term at the position specified in the list of Sunipotents
     */
    public Sunipotent get(int index) {
	return product.get(index);
    }

    /**
     * Get the last (rightmost) term in the product of sunipotents.
     * 
     * @return the last sunipotent
     */
    public Sunipotent getLast() {
	if (product.size() == 0)
	    return null;
	return product.get(product.size() - 1);
    }

    /**
     * Gets the polynomial argument of the ith term.
     * 
     * @param i
     *            integer, index of term
     * @return the polynomial argument of this term, or null if the index is out
     *         of range.
     */
    public Polynomial getArg(int i) {
	return (-1 < i && i < product.size()) ? get(i).getArgument() : null;

    }

    /**
     * Gets the number of terms in the product of Sunipotents.
     * 
     * @return the number of Sunipotents in this Unipotent
     */
    public int getNumberOfTerms() {
	return product.size();
    }

    /**
     * Returns the ambient root system in which this Unipotent lives.
     * 
     * @return the root system for which this Unipotent is an element of
     */
    public Group getGroup() {
	return this.group;
    }

    /**
     * Finds the first sunipotent in the product that has the specified root. If
     * such a sunipotent cannot be found in the product, -1 is returned.
     * 
     * @param root
     *            the root to search for
     * @return the position of the specified root or -1 if not found
     */
    public int indexOf(int[] root) {
	for (int i = 0; i < product.size(); i++)
	    if (Arrays.equals(product.get(i).getRoot(), root))
		return i;
	return -1;
    }

    /**
     * Finds the last sunipotent in the product that has the specified root. If
     * such a sunipotent cannot be found in the product, -1 is returned.
     * 
     * @param root
     *            the root to search for
     * @return the position of the specified root or -1 if not found
     */
    public int lastIndexOf(int[] root) {
	for (int i = product.size() - 1; i > -1; i--)
	    if (Arrays.equals(product.get(i).getRoot(), root))
		return i;
	return -1;
    }

    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots. If no sunipotent element in the product can
     * be found, -1 is returned. Search sunipotents left to right, roots in
     * listed order.
     * 
     * 
     * @param roots
     *            the list of roots to search for
     * @return the index of the first sunipotent from the left that matches r0,
     *         where r0 is the first root in the specified list which has a
     *         match, or -1 if none of the roots in the list has a match.
     */
    public int indexOf(int[][] roots) {
	for (int i = 0; i < product.size(); i++)
	    for (int j = 0; j < roots.length; j++)
		if (Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;
	return -1;
    }

    /**
     * If u = x_{a_1}(r_1) ... x_{a_N}(r_N) is a unipotent and m is an int[][],
     * then u.indexOf(m) is the smallest integer i with the property that a_i is
     * an element of m.
     * 
     * @param roots
     *            list of roots to check for
     * @return the index of the first term whose root is on the given list.
     */
    public int indexOf(List<int[]> roots) {
	for (int i = 0; i < product.size(); i++)
	    for (int j = 0; j < roots.size(); j++)
		if (Arrays.equals(get(i).getRoot(), roots.get(j)))
		    return i;
	return -1;
    }

    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots, starting from the specified point. If no
     * sunipotent element in the product can be found, -1 is returned. Search
     * sunipotents left to right, roots in listed order.
     * 
     * 
     * @param roots
     *            the list of roots to search for
     * @param startPoint
     *            the place to start looking
     * @return the index of the first sunipotent from the left that matches r0,
     *         where r0 is the first root in the specified list which has a
     *         match, or -1 if none of the roots in the list has a match.
     */
    public int indexOf(final int[][] roots, final int startPoint) {
	for (int i = startPoint; i < product.size(); i++)
	    for (int j = 0; j < roots.length; j++)
		if (Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;
	return -1;
    }

    /**
     * Tries to find a sunipotent in the product that has a root that matches
     * any of the specified roots. If no sunipotent element in the product can
     * be found, -1 is returned. Search roots in listed order, sunipotents right
     * to left.
     * 
     * @param roots
     *            the list of roots to search for
     * @return the index of the last sunipotent that matches any of the roots in
     *         the specified list or -1 if no such sunipotent element can be
     *         found
     */
    public int lastIndexOf(int[][] roots) {
	for (int i = product.size() - 1; i > -1; i--)
	    for (int j = 0; j < roots.length; j++)
		if (Arrays.equals(get(i).getRoot(), roots[j]))
		    return i;

	return -1;
    }

    private boolean isMobile(int i) {
	return !immobile.contains(product.get(i));
    }

    private void preFix() {

	int i = 0;
	while (i < product.size() - 1) {
	    int j = i + 1;
	    while (j < product.size()) {
		if (Arrays.equals(product.get(i).getRoot(), product.get(j)
			.getRoot())) {

		    fix(i, j);
		    /*
		     * fix(i,j) will leave terms 0 through i-1 alone. However,
		     * it may: - push the ith term right so that the i+1st term
		     * or a new term created by conjugation becomes the ith
		     * term. - create new terms between i and j, which have not
		     * yet been compared to the terms in positions 0 through i.
		     */
		    j = Math.max(i, 1); // this is the first term which may be
		    // new,
		    i = 0; // we put i back to 0, so that all new terms will be
		    // checked against all old terms.
		    // this is modestly inefficient, since it re-checks some
		    // pairs already checked.
		    // However, it does ensure that every pair is checked.

		} else
		    j++;
	    }
	    i++;
	}
    }

    /**
     * Shifts sunipotent at the given index to the left all the way to the end
     * of the list.
     * 
     * @param index
     *            the index of the sunipotent to be pushed
     * @return the final position of the sunipotent
     */
    public int pushFarLeft(int index) {
	while (index > 0) {
	    index = pushLeft(index);
	}
	return index;
    }

    /**
     * Pushes the given sunipotent all the way to the left, removes it, then
     * calls cleanUp.
     * 
     * @param index
     *            the sunipotent to be moved.
     */
    public void pushFarLeftAndRemove(int index) {
	if (pushFarLeft(index) == 0)
	    remove(0);
	cleanUp();
    }

    /**
     * Shifts sunipotent at the given index to the right all the way to the end
     * of the list.
     * 
     * @param index
     *            the index of the sunipotent to be pushed
     * @return the final position of the sunipotent
     */
    public int pushFarRight(int index) {
	while (index < product.size() - 1) {
	    index = pushRight(index);
	}
	return index;
    }

    /**
     * Pushes the given sunipotent all the way to the right, removes it, then
     * calls cleanUp.
     * 
     * @param index
     *            the sunipotent to be moved.
     */
    public void pushFarRightAndRemove(int index) {
	if (pushFarRight(index) == product.size() - 1)
	    remove(product.size() - 1);
	cleanUp();
    }

    /**
     * Shifts Sunipotent at given index to the left by one. If this commutation
     * requires the addition of new terms, they are properly inserted.
     * 
     * 
     * @param index
     *            the element to be pushed left
     * @return the location of the element that was pushed left, or -1 in the
     *         case of cancellation.
     */
    public int pushLeft(int index) {
	index--;
	if (index >= product.size() - 1 || index < 0)
	    throw new IndexOutOfBoundsException();
	int[] a = product.get(index).getRoot();
	int[] b = product.get(index + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(index).getArgument().plus(
		    product.get(index + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		/*
		 * replace Suni at index with a new Suni. (simply modifying the
		 * polynomial of this Sunipotent will break old code which does
		 * something while product contains existing one... )
		 */
		// manage associations
		Sunipotent newSuni = Sunipotent.create(product.get(index)
			.getRoot(), newPoly);
		associate(newSuni, associations.get(product.get(index)));
		associate(newSuni, associations.get(product.get(index + 1)));

		if (!(isMobile(index) && isMobile(index + 1)))
		    immobile.add(newSuni);

		product.set(index, newSuni);
		// suni at index absorbs the one at index+1, so remove the one
		// at index+1
		remove(index + 1);
		if (!(isMobile(index) && isMobile(index + 1)))
		    immobile.add(newSuni);
		return index;
	    } else // terms cancel
	    {
		remove(index + 1);
		remove(index);
		return -1;
	    }

	}
	List<Sunipotent> ab = group.commutator(product.get(index), product
		.get(index + 1));
	product.addAll(index, ab);

	index = index + ab.size();
	Collections.swap(product, index, index + 1);
	return index;
    }

    /**
     * Shifts Sunipotent at given index to the left by one. If this commutation
     * requires the addition of new terms, they are properly inserted.
     * 
     * 
     * @param from
     *            the element to be pushed left
     * @param to
     *            the location it is being pushed towards
     * @return the location of the element that was pushed left, or -1 in the
     *         case of cancellation.
     */
    public int[] pushLeftPair(int from, int to) {
	from--;

	int[] pair = new int[2];
	pair[0] = from;
	pair[1] = to;
	if (from >= product.size() - 1 || from < 0)
	    throw new IndexOutOfBoundsException();
	int[] a = product.get(from).getRoot();
	int[] b = product.get(from + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(from).getArgument().plus(
		    product.get(from + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		/*
		 * replace Suni at index with a new Suni. (simply modifying the
		 * polynomial of this Sunipotent will break old code which does
		 * something while product contains existing one... )
		 */
		// manage associations
		Sunipotent newSuni = Sunipotent.create(product.get(from)
			.getRoot(), newPoly);
		associate(newSuni, associations.get(product.get(from)));
		associate(newSuni, associations.get(product.get(from + 1)));

		if (!(isMobile(from) && isMobile(from + 1)))
		    immobile.add(newSuni);

		product.set(from, newSuni);
		// suni at index absorbs the one at index+1, so remove the one
		// at index+1
		remove(from + 1);
		if (!(isMobile(from) && isMobile(from + 1)))
		    immobile.add(newSuni);
		return pair;
	    } else // terms cancel
	    {
		remove(from + 1);
		remove(from);
		pair[1] = pair[0];
		return pair;
	    }

	}
	List<Sunipotent> ab = group.commutator(product.get(from), product
		.get(from + 1));
	product.addAll(from, ab);

	from = from + ab.size();
	Collections.swap(product, from, from + 1);
	return pair;
    }

    /**
     * Shifts Sunipotent at given index to the right by one. If this commutation
     * requires the addition of new terms, they are properly inserted. If the
     * next sunipotent right has the same root, then the two are combined.
     * 
     * @param index
     *            the index of the term to be pushed to the right by one
     * @return the location of the element that was shifted right, except in the
     *         case of cancellation. In that case, it returns index. (Note that
     *         if the last two terms cancel, this will NOT be the index of an
     *         element of the unipotent).
     */
    public int pushRight(int index) {

	if (index >= product.size() - 1 || index < 0) {
	    throw new IndexOutOfBoundsException();
	}
	int[] a = product.get(index).getRoot();
	int[] b = product.get(index + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(index).getArgument().plus(
		    product.get(index + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		Sunipotent newSuni = Sunipotent.create(product.get(index)
			.getRoot(), newPoly);
		associate(newSuni, associations.get(product.get(index)));
		associate(newSuni, associations.get(product.get(index + 1)));

		if (!(isMobile(index) && isMobile(index + 1)))
		    immobile.add(newSuni);

		product.set(index, newSuni);
		remove(index + 1);
		return index;
	    } else {
		remove(index + 1);
		remove(index);
		return product.size();
	    }

	}

	List<Sunipotent> ab = group.commutator(product.get(index), product
		.get(index + 1));
	product.addAll(index, ab);

	index = index + ab.size();

	Collections.swap(product, index, index + 1);
	return index + 1;

    }

    /**
     * Shifts Sunipotent at given index to the right by one. If this commutation
     * requires the addition of new terms, they are properly inserted. If the
     * next sunipotent right has the same root, then the two are combined.
     * 
     * @param from
     *            the index of the term to be pushed to the right by one
     * @param to
     *            the target towards which it is being pushed
     * @return the location of the element that was shifted right, except in the
     *         case of cancellation. In that case, it returns index. (Note that
     *         if the last two terms cancel, this will NOT be the index of an
     *         element of the unipotent).
     */
    public int[] pushRightPair(int from, int to) {
	int[] a = product.get(from).getRoot();
	int[] b = product.get(from + 1).getRoot();
	if (Arrays.equals(a, b)) {
	    Polynomial newPoly = product.get(from).getArgument().plus(
		    product.get(from + 1).getArgument());
	    if (newPoly != Polynomial.create(0)) {
		Sunipotent newSuni = Sunipotent.create(product.get(from)
			.getRoot(), newPoly);
		associate(newSuni, associations.get(product.get(from)));
		associate(newSuni, associations.get(product.get(from + 1)));

		if (!(isMobile(from) && isMobile(from + 1)))
		    immobile.add(newSuni);

		product.set(from, newSuni);
		remove(from + 1);
		return pair(from, to - 1);
	    } else {
		remove(from + 1);
		remove(from);
		return pair(product.size(), product.size());
	    }

	}

	List<Sunipotent> ab = group.commutator(product.get(from), product
		.get(from + 1));
	product.addAll(from, ab);

	from = from + ab.size();

	Collections.swap(product, from, from + 1);
	return pair(from + 1, to + ab.size());

    }

    private int[] pair(int i, int j) {
	int[] ans = new int[2];
	ans[0] = i;
	ans[1] = j;
	return ans;
    }

    /**
     * @param from
     *            index of sunipotent to move
     * @param to
     *            location it should be moved to. TODO add precision
     */
    /*
     * called by SectionIntegral.move only..
     */
    public void new_move(int from, int to) {
	if (to > product.size() - 1)
	    pushFarRight(from);
	else {
	    while (from != to) {
		int[] pair = push(from, to);
		from = pair[0];
		to = pair[1];
	    }// end while from != to
	}// end if to > product.size() else

    }

    /**
     * Move Sunipotent from position "from" to position "to." First assume that
     * the Sunipotents at positions from and to appear only once each in the
     * product. Assume further that no other Sunipotent has the same root as the
     * one at from. Then the Sunipotent at position from will be pushed in the
     * direction of position to until it is at position to among terms from the
     * Unipotent. If to < from this means the Sunipotent in question is actually
     * at position to. If to > from, then pushing our Sunipotent to the right
     * may produce additional terms from commutators. When we say that the
     * Sunipotent should be at position to
     * "among terms from the original Unipotent," we mean not counting these
     * terms from commutators.
     * 
     * Now assume that there are other Sunipotents in the product with the same
     * root as the one at from. This only changes things if they come between
     * from and to. In this case, as we push our Sunipotent towards position
     * "to", it will combine and possibly cancel with these additional terms. If
     * it combines with a term, this in effect decreases the number of terms by
     * one, and we also decrease the target "to" by one. If our Sunipotent
     * cancels away completely, then it is adjudged to have reached its goal.
     * 
     * Now assume that the Sunipotents at from and to appear more than once in
     * the product. Then this method will not terminate until all occurrences of
     * the Suni
     * 
     * @param from
     *            position of Sunipotent to move
     * @param to
     *            position one wishes that Sunipotent to be in. As terms are
     *            combined because they have the same root, or new terms are
     *            introduced by commutators, this target position will be
     *            revised so that it is always the same relative to the
     *            remaining original terms
     */
    public void move(int from, int to) {
	if (to > product.size() - 1)
	    pushFarRight(from);
	else {
	    Sunipotent movedOne = product.get(from);
	    Sunipotent currentlyAtTo = product.get(to);

	    boolean done = false;
	    while (!done) {
		done = true;
		if (product.indexOf(movedOne) > product.indexOf(currentlyAtTo)) {
		    this.pushLeft(product.indexOf(movedOne));
		    done = false;
		}
		if (product.indexOf(movedOne) < product.indexOf(currentlyAtTo) - 1) {
		    done = false;
		    this.pushRight(product.indexOf(movedOne));
		}
	    }// end while not done
	}// end if to > product.size() else

    }

    private int[] push(int from, int to) {
	if (from < to)
	    return pushRightPair(from, to);
	else
	    return pushLeftPair(from, to);

    }

    /**
     * Removes the i-th term in this Unipotent.
     * 
     * @param i
     *            the index of the term to be removed.
     */
    public void remove(int i) {
	if (associations.containsKey(product.get(i)))
	    associations.remove(product.get(i));
	if (!isMobile(i))
	    immobile.remove(get(i));
	product.remove(i);
    }

    /**
     * Remove a Sunipotent term.
     * 
     * @param s
     *            the Sunipotent to be removed
     */
    public void remove(final Sunipotent s) {
	if (associations.containsKey(s))
	    associations.remove(s);
	immobile.remove(s);
	product.remove(s);
    }

    /**
     * Simplifies the unipotent, by making substitutions based on the
     * associations between Sunipotents and variables. Records the effect of
     * these substitutions on a given polynomial.
     * 
     * @param p
     *            a polynomial
     * @return the polynomial p after a number of substitutions have been made,
     *         based on the associations stored in this unipotent.
     * @throws BadSubstitutionException
     *             if any substitution is made for a variable which appears to a
     *             negative exponent.
     */
    public Polynomial chOfVars(Polynomial p) throws BadSubstitutionException {
	/*
	 * This is probably a good place to remind the reader that an object of
	 * class Unipotent stores a list of associations between Strings
	 * (thought of as variables) and Sunipotents. This method is the sort of
	 * thing for which these associations are intended.
	 * 
	 * Not every Sunipotent will be associated to a variable, and not every
	 * variable will be associated to a Sunipotent. In order for things to
	 * work properly, no Sunipotent may be associated to more than one
	 * variable and no variable may be associated to more than one
	 * Sunipotent.
	 * 
	 * In this method, if a Sunipotent is associated to a variable s, then
	 * the method tries to make an appropriate substitution so that, after
	 * substitution the argument of the Sunipotent is s.
	 */
	for (int i = 0; i < getNumberOfTerms(); i++) {

	    /*
	     * get the String associated to Sunipotent i, (If Sunipotent i has
	     * no String, then stringOf() returns "null."
	     */
	    String s1 = stringOf(get(i));

	    if (s1 != null) {// i.e., if our Sunipotent is indeed associated to
		// a variable...

		/*
		 * there are two cases that can be handled. Write arg = current
		 * argument of our Sunipotent. 1. arg = s1 + q, where q is
		 * independent of s1. In this case, the substitution s1 -> s1 -
		 * q is indicated. 2. arg = -s1+q. In this case, the
		 * substitution s1 -> (-s1+q) is indicated.
		 */
		// rewrite condition 1. above as
		// "q:= arg - s1 is independent of s1."
		if (get(i).getArgument().minus(Polynomial.create(s1))
			.isIndependentOf(s1)) {

		    // p1:= s1-q = 2 s1 - arg.
		    Polynomial p1 = Polynomial.create(s1).times(2).minus(
			    get(i).getArgument());

		    // s1 -> p1
		    p = p.replace(s1, p1); // in the Polynomial p which was
		    // passed to this method by the
		    // caller,
		    this.substitute(s1, p1);// and in this Unipotent. This will
		    // destroy the association involving
		    // s1.
		    this.associate(get(i), s1);// Restore the association
		    // between the ith Sunipotent and
		    // s1.
		}
		// rewrite condition 2. above as q:= arg + s1 is independent of
		// s1."
		if (get(i).getArgument().plus(Polynomial.create(s1))
			.isIndependentOf(s1)) {

		    // p1:= -s1+q = arg.
		    Polynomial p1 = get(i).getArgument();

		    // s1 -> p1
		    p = p.replace(s1, p1); // in the Polynomial p which was
		    // passed to this method by the
		    // caller,
		    this.substitute(s1, p1);// and in this Unipotent
		    this.associate(get(i), s1);// Restore the association
		    // between the ith Sunipotent and
		    // s1.

		}

	    }// end if s1 not null

	}// end for each term...
	return p;
    }// end ChOfVars

    /**
     * Replaces a given String variable by a given Polynomial throughout.
     * Immobility is preserved. Any term which is associated to a variable which
     * is not s1 will remain associated to that variable. A term which is
     * associated to s1 will no longer have an associated variable, unless p1 is
     * itself a variable, in which case it will inherit s1's association.
     * 
     * @param s1
     *            varible, for which to substitute
     * @param p1
     *            to plug in for s1
     * @throws BadSubstitutionException
     *             if s1 appears to a negative exponent and p1 is not a signed
     *             monomial
     */
    public void old_substitute(String s1, Polynomial p1)
	    throws BadSubstitutionException {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for (int i = 0; i < product.size(); i++) {
	    Polynomial arg = get(i).getArgument();
	    Polynomial newArg = arg.replace(s1, p1);
	    String associate = stringOf(get(i));
	    Sunipotent replacement = Sunipotent
		    .create(get(i).getRoot(), newArg);
	    newProduct.add(replacement);
	    if (!isMobile(i)) {

		newImmobile.add(replacement);
	    }
	    if (associate != null && !associate.equals(s1)) {
		newAssociations.put(replacement, associate);
	    }
	    if (associate == s1 && p1.isAVariable()) {
		newAssociations.put(replacement, p1.getVar());
	    }
	}
	product.removeAll(product);
	product.addAll(newProduct);
	associations = newAssociations;
	immobile.removeAll(immobile);
	immobile.addAll(newImmobile);

    }

    /**
     * Replaces a given String variable by a given Polynomial throughout.
     * Immobility is preserved. Any term which is associated to a variable which
     * is not s1 will remain associated to that variable. A term which is
     * associated to s1 will no longer have an associated variable, unless p1 is
     * itself a variable, in which case it will inherit s1's association.
     * 
     * @param s1
     *            variable, for which to substitute
     * @param p1
     *            to plug in for s1
     * @throws BadSubstitutionException
     *             if s1 appears to a negative exponent and p1 is not a signed
     *             monomial
     */
    public void substitute(String s1, Polynomial p1)
	    throws BadSubstitutionException {
	for (int i = 0; i < product.size(); i++) {
	    Polynomial arg = get(i).getArgument();
	    if (arg.dependsOn(s1)) {
		Polynomial newArg = arg.replace(s1, p1);
		Sunipotent newSuni = Sunipotent
			.create(get(i).getRoot(), newArg);
		replace(i, newSuni);
	    }// end if arg depends on s1
	}// end for i = 0 to product.size

    }// end new_substitute

    /**
     * Replace given String variable by given Polynomial throughout.
     * 
     * @param s1
     *            variable
     * @param s2
     *            to be substituted
     */
    public void substitute(String s1, String s2) {
	for (int i = 0; i < product.size(); i++) {
	    Polynomial arg = get(i).getArgument();
	    if (arg.dependsOn(s1)) {
		Polynomial newArg = arg.replace(s1, s2);
		Sunipotent newSuni = Sunipotent
			.create(get(i).getRoot(), newArg);
		replace(i, newSuni);
	    }// end if arg depends on s1
	}// end for i = 0 to product.size

    }// end new_substitute

    /**
     * This method, together with the machinery of "associations" facilitates
     * certain change of variables algorithms. Suppose the Sunipotent x_a(r_a)
     * is associated to the default variable r_a. Then, in most situations
     * rather than allow some algebraic manipulation to complicate the argument
     * of x_a, we shall simply make a substitution for r_a to insure that the
     * argument of x_a is always r_a. For purpose of such manipulations, it
     * makes sense to simply skip the term x_a(r_a).
     * 
     * @param s1
     *            variable for which a substitution is made.
     * @param p1
     *            plugged in
     * @param j
     *            term to skip
     * @throws BadSubstitutionException
     *             if s1 appears with a negative exponent.
     */
    public void substituteWithAnException(String s1, Polynomial p1, int j)
	    throws BadSubstitutionException {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for (int i = 0; i < product.size(); i++) {

	    Polynomial arg = get(i).getArgument();
	    Polynomial newArg;
	    if (i != j) {
		newArg = arg.replace(s1, p1);
	    } else
		newArg = arg;
	    String associate = stringOf(get(i));
	    Sunipotent replacement = Sunipotent
		    .create(get(i).getRoot(), newArg);
	    newProduct.add(replacement);
	    if (!isMobile(i)) {

		newImmobile.add(replacement);
	    }
	    if (associate != null) {
		newAssociations.put(replacement, associate);
	    }

	}
	product.removeAll(product);
	product.addAll(newProduct);
	associations = newAssociations;
	immobile.removeAll(immobile);
	immobile.addAll(newImmobile);

    }

    /**
     * Returns a string representation of this Unipotent.
     * 
     * @see java.lang.Object#toString()
     */

    public String toString() {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0; i < product.size(); i++) {
		if (currentLineLength + product.get(i).toString().length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH) {
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > ..
		sb.append(product.get(i).toString() + " ");
		currentLineLength += 1 + product.get(i).toString().length();
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }

    /**
     * Returns a string representation of the unipotent, making use of the
     * toString method for class Sunipotent which supports abbreviation.
     * 
     * @param abbreviated
     *            indicates whether Sunipotent terms will be displayed in
     *            abbreviated format
     * @return string representation
     */
    public String toString(final boolean abbreviated) {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0; i < product.size(); i++) {
		String nextTerm = product.get(i).toString(abbreviated);
		if (currentLineLength + nextTerm.length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH) {
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > ..
		sb.append(nextTerm + " ");
		currentLineLength += 1 + nextTerm.length();
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }

    /**
     * Returns a string representation of this Unipotent in a tabular format
     * with the index of each Sunipotent indicated.f
     * 
     * TODO look around for something to facilitate output that looks at how
     * long the lines are and puts breaks when it needs to.
     * 
     * @return String representation
     * 
     * @see java.lang.Object#toString()
     */
    public String toStringWithIndices() {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0; i < product.size(); i++) {
		if (currentLineLength + product.get(i).toString().length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH) {
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > ..
		sb.append(i + " " + product.get(i).toString() + "  ");
		currentLineLength += 3 + product.get(i).toString().length()
			+ (int) Math.floor(Math.log10(Math.max(1, i)));
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }

    /**
     * Returns a string representation of the unipotent in which indices are
     * indicated, and abbreviated notation for simple unipotents can be employed
     * by indicating as much with a boolean parameter.
     * 
     * @param abbreviated
     *            indicates whether to employ abbreviated notation
     * @return string
     */
    public String toStringWithIndices(final boolean abbreviated) {
	if (product.size() != 0) {
	    int currentLineLength = 0;
	    StringBuffer sb = new StringBuffer();
	    for (int i = 0; i < product.size(); i++) {
		if (currentLineLength
			+ product.get(i).toString(abbreviated).length() > edu.siu.math.egut.io.Constants.SCREEN_WIDTH) {
		    sb.append("\n");
		    currentLineLength = 0;
		}// end if currentlinelength + .. > ..
		sb
			.append(i + " " + product.get(i).toString(abbreviated)
				+ "  ");
		currentLineLength += 3
			+ product.get(i).toString(abbreviated).length()
			+ (int) Math.floor(Math.log10(Math.max(1, i)));
	    }
	    return sb.toString();
	} else {
	    return "(empty unipotent)";

	}
    }

    /**
     * Gets the string associated to the given Sunipotent (which may be null)
     * 
     * @param suni
     *            Sunipotent
     * @return associated string if there is one, or null.
     */
    public String stringOf(Sunipotent suni) {
	return associations.get(suni);
    }

    /**
     * Gets the sunipotent associated to the given strong (which may be null)
     * 
     * @param s
     *            String
     * @return assocatated Sunipotent, or null if there is none.
     */
    public Sunipotent suniOf(String s) {

	return associations.getKey(s);
    }

    /**
     * @return true if any of the arguments of the terms has a negative exponent
     */
    public boolean hasNegativeExponents() {
	for (final Sunipotent s : this.getTerms())
	    if (s.hasNegativeExponents())
		return true;
	return false;
    }

    /**
     * Checks for Sunipotents with argument zero and removes any that it finds.
     */
    public void clearZeros() {
	int i = 0;
	while (i < product.size()) {
	    if (product.get(i).getArgument() == Polynomial.create(0)) {
		associations.removeValue(product.get(i));
		immobile.remove(product.get(i));
		product.remove(i);
	    } else
		i++;
	}

    }

    /**
     * Gets the index of the given Sunipotent. If u is a unipotent, then it is a
     * product of Sunipotents s_1 s_2 .... s_N.
     * 
     * If s is a Sunipotent, then u.getIndex(s) is equal to i if s == s_i, and
     * -1 if s does not appear in u.
     * 
     * @param sunipotent
     *            whose location in our Unipotent is desired
     * @return i if the given Sunipotent appears at position i in our unipotent,
     *         and -1 if it does not appear.
     */
    public int getIndex(final Sunipotent sunipotent) {
	return product.indexOf(sunipotent);
    }

    /**
     * Serialization and deserialization can sometimes allow Sunipotents to
     * sneak into existence without being entered into the Sunipotent store.
     * This corrects that problem.
     * 
     * @return a Unipotent with the same underlying data, in which every
     *         Sunipotent has been run through Sunipotent.update()
     */
    public Unipotent update() {
	for (int i = 0; i < product.size(); i++) {

	    final Sunipotent s1 = Sunipotent.update(get(i));
	    if (immobile.contains(get(i))) {
		immobile.remove(get(i));
		immobile.add(s1);

	    }
	    if (stringOf(get(i)) != null) {
		associate(s1, stringOf(get(i)));
		disassociate(get(i));
	    }
	    product.remove(i);
	    product.add(i, s1);

	}
	return this;

    }

    /*
     * The remaining methods are only used in EGUT program SectionIntegral which
     * is currently at a very early stage of development. I am not convinced
     * that they will make it into the final version.
     */

    /**
     * Modifies the unipotent according to the adjoint action of a specified
     * group element.
     * 
     * 
     * @param string
     *            should be readable as a group element
     * @throws NoSuchElementException
     *             if the given string is not readable as a group element
     */
    public void actBy(final String string) throws NoSuchElementException {
	/*
	 * For now we support two types of group elements: simple unipotents and
	 * Weyl elements.
	 */
	// if the String is readable as a simple unipotent
	Sunipotent s = Sunipotent.readWithChecks(string, group);
	if (s != null) {
	    actBy(s);
	} else {
	    // try to read the string as a Weyl element and act by that element
	    // if successful.
	    if (Algorithms
		    .representsWeylWord(edu.siu.math.egut.io.Algorithms
			    .removeWhiteSpaceCommasAndBrackets(string), group
			    .getRank())) {
		actByWord(string);
	    } else
		throw new NoSuchElementException();
	}

    }

    /**
     * Conjugates the unipotent by a word in the standard representatives for
     * the simple reflections in the Weyl group.
     * 
     * @param wordString
     *            a string, interpreted as a word in the simple reflections,
     *            with each digit being an individual reflection. An error will
     *            result if any character is not a digit between 1 and the rank
     *            of the ambient group.
     */
    public void actByWord(final String wordString) {

	for (int i = 0; i < product.size(); i++) {
	    Sunipotent newSuni = get(i).imageUnder(wordString);
	    if (isMobile(i)) {
		immobile.remove(get(i));
		immobile.add(newSuni);
	    }
	    if (stringOf(get(i)) != null) {
		associate(newSuni, stringOf(get(i)));
	    }
	    product.remove(i);
	    product.add(i, newSuni);

	}

    }

    /**
     * Acts by the (inner automorphism attached to) the given Sunipotent s. If u
     * is a unipotent and s is a Sunipotent then u.actBy(s) is the Unipotent
     * representing s u s^{-1} (after some simplification).
     * 
     * @param s
     *            to act.
     */
    public void actBy(final Sunipotent s) {

	leftMultiply(s);
	this.rightMultiply(Sunipotent.create(s.getRoot(), s.getArgument()
		.times(-1)));
	cleanUp();
	this.clearZeros();

    }

    /**
     * Reads String representation of Unipotent and returns the desired object.
     * This method is deliberately non-fault-tolerant: it is used mainly to read
     * plaintext setup files. If the setup file is not formatted correctly, the
     * desired behavior is generally to terminate, so that the user can fix the
     * setup file and try again.
     * 
     * @param s
     *            representing Unipotent
     * @return represented by s
     * @throws UnipotentReadException
     *             if input can not be read
     */
    public static Unipotent read(String[] s) throws UnipotentReadException {
	if (s.length == 0)
	    return null;
	if (!edu.siu.math.egut.io.Algorithms.SUNIPOTENT_OF_UNSPECIFIED_RANK
		.matcher(s[0]).matches())
	    throw new UnipotentReadException();
	Sunipotent s1 = Sunipotent.read(s[0]);
	if (s1 == null)
	    throw new UnipotentReadException();
	Group group = Group.getGroup(s1.getRoot().length);
	ArrayList<Sunipotent> prod = new ArrayList<Sunipotent>();
	prod.add(s1);
	for (int i = 1; i < s.length; i++)
	    if (edu.siu.math.egut.io.Algorithms.suniString(group).matcher(s[i])
		    .matches()) {
		Sunipotent si = Sunipotent.readWithChecks(s[i], group);
		if (si == null)
		    throw new UnipotentReadException();
		prod.add(si);
	    }

	return new Unipotent(group, prod);

    }

    /**
     * @param string
     *            representing Unipotent in roots, prefix format
     * @return pair consisting of desired Unipotent and prefix
     * @throws NotARootException
     *             if "roots" portion of String contains a non-root
     * @throws UnipotentReadException
     *             if String is not of a recognizable InputStyle
     * @deprecated The idea of working with "prefixes" beyond the input format
     *             itself has been essentially abandoned.
     */
    public static UnipotentPrefixPair read(String string)
	    throws NotARootException, UnipotentReadException {
	if (inputStyle(string) != InputStyle.NONSENSE)
	    return read(string, inputStyle(string));
	throw new UnipotentReadException();

    }

    private static UnipotentPrefixPair read(String string, InputStyle inputStyle)
	    throws NotARootException {
	switch (inputStyle) {
	case ROOTS_PLUS_STRING:
	    return new UnipotentPrefixPair(new Unipotent(parseRoots(string),
		    parseString(string)), string);

	}
	return null;

    }

    private static String parseString(String string) {
	return string.substring(string.indexOf("prefix") + 6).trim();
    }

    private static int[][] parseRoots(String string) {
	return edu.siu.math.egut.io.Algorithms.readLiEMatrix(string);
    }

    private static InputStyle inputStyle(String string) {
	if (ROOTS_PLUS_STRING_PATTERN.matcher(string).matches())
	    return InputStyle.ROOTS_PLUS_STRING;
	return InputStyle.NONSENSE;
    }

    /**
     * 
     * @param sty
     *            TEX or SCREEN (anything else is defaulted to SCREEN)
     * @return a string representation of this Unipotent in a specified
     *         OutputStyle.
     */
    public String toString(OutputStyle sty) {
	switch (sty) {
	case TEX:
	    StringBuilder sb = new StringBuilder("\\begin{array}{l}");
	    int width = 0;
	    for (Sunipotent s : this.product) {
		if (width > 0
			&& width + s.toString(OutputStyle.SCREEN).length() > PAGE_WIDTH) {
		    sb.append("\\\\\n");
		    width = 0;
		}
		sb.append(s.toString(OutputStyle.TEX));
		width = width + s.toString(OutputStyle.SCREEN).length();
	    }
	    sb.append("\\end{array}");
	    return sb.toString();

	}
	return this.toString();
    }

    /**
     * @param sty
     *            indicating format output should be in
     * @param abbreviated
     *            true if abbreviation should be used
     * @return string representation of sunipotent in given output style,
     *         possibly abbreviated
     */
    public String toString(final OutputStyle sty, final boolean abbreviated) {
	switch (sty) {
	case TEX:
	    StringBuilder sb = new StringBuilder("\\begin{array}{l}");
	    int width = 0;
	    for (Sunipotent s : this.product) {
		if (width > 0
			&& width
				+ s.toString(OutputStyle.SCREEN, abbreviated)
					.length() > PAGE_WIDTH) {
		    sb.append("\\\\\n");
		    width = 0;
		}
		sb.append(s.toString(OutputStyle.TEX, abbreviated));
		width = width
			+ s.toString(OutputStyle.SCREEN, abbreviated).length();
	    }
	    sb.append("\\end{array}");
	    return sb.toString();

	}
	return this.toString();
    }

    /**
     * @param x
     *            variable
     * @return true if the argument of each term in the product is independent
     *         of x.
     */
    public boolean isIndependentOf(String x) {
	for (Sunipotent s : this.product) {
	    if (s.getArgument().dependsOn(x))
		return false;
	}
	return true;
    }

    /**
     * Replaces one Sunipotent with another throughout the Unipotent.
     * 
     * @param s
     *            existing Sunipotent
     * @param s1
     *            replacement
     */
    public void replace(final Sunipotent s, final Sunipotent s1) {
	for (int i = 0; i < product.size(); i++)
	    if (product.get(i) == s) {
		product.add(i, s1);
		product.remove(i + 1);
	    }

    }

    /**
     * Removes the term at a specifed index and replaces it with a given new
     * term.
     * 
     * @param i
     *            the index.
     * @param s1
     *            the new term.
     */
    public void replace(int i, Sunipotent s1) {
	if (!isMobile(i)) {
	    immobile.remove(get(i));
	    immobile.add(s1);
	}
	if (stringOf(get(i)) != null) {
	    associate(s1, stringOf(get(i)));
	}
	product.add(i, s1);
	product.remove(i + 1);

    }

    /**
     * Sends a String representation of all associations to System.out.
     */
    public void listAssociations() {
	if (associations.isEmpty())
	    System.out.println("no associations.");

	ArrayList<int[]> assocRoots = new ArrayList<int[]>();
	for (Sunipotent s : associations.keySet()) {
	    System.out.println(s.toString() + "<--->" + stringOf(s));
	    assocRoots.add(s.getRoot());
	}
	System.out.println(associations.size() + " associations");
	System.out.println(edu.siu.math.egut.io.Algorithms
		.writeLieMatrix(assocRoots));

    }

    /**
     * @param u
     *            to be copied
     * @return a new Unipotent with the same underlying data.
     */
    public static Unipotent copyOf(final Unipotent u) {
	return new Unipotent(u.product, u.group, u.immobile, u.associations);
    }

    /**
     * Checks equality of products of sunipotents. Two unipotents are equal if
     * and only if their lists of terms are identical. (1) Unipotent objects
     * having the same terms, but different immobile or association data will be
     * equal (2) This method does not check for algebraic identities between
     * non-identical products.
     * 
     * @param u
     *            to check equality with
     * @return true, if the two unipotents have all the same terms.
     */
    public boolean equals(final Unipotent u) {
	if (u.getNumberOfTerms() != this.getNumberOfTerms())
	    return false;
	for (int i = 0; i < u.getNumberOfTerms(); i++)
	    if (!get(i).equals(u.get(i)))
		return false;
	return true;

    }

    /**
     * Acts by (the inner automorphism attached to) the standard representative
     * for a Weyl word.
     * 
     * @param word
     *            should represent a Word in the relevant Weyl group.
     */
    public void actBy(int[] word) {
	for (int i = word.length - 1; i > -1; i--) {
	    actBy(word[i]);
	}

    }
    
    /**
     * Act on the Unipotent by a WeylWord in the same group.
     * @param w which acts
     */
    public void actBy(final WeylWord w){
	actBy(w.getWord());
    }

    /**
     * Add given list of Sunipotents to the product at the right. All new terms
     * are immobile. If a new term has a variable for an argument, and if that
     * variable is not already associated to some other term, then an
     * association is created between the new sunipotent and its variable.
     * 
     * @param newSunipotents
     *            to be added
     */
    public void addRight(final ArrayList<Sunipotent> newSunipotents) {
	for (Sunipotent s : newSunipotents) {
	    product.add(s);
	    if (s.getArgument().isAVariable()
		    && suniOf(s.getArgument().getVar()) == null)
		associate(s, s.getArgument().getVar());
	    immobile.add(s);
	}

    }

    /**
     * Replace given String variable by given Polynomial throughout.
     * 
     * @param s1
     *            variable
     * @param p1
     *            to be substituted
     */
    public void old_substitute(final String s1, final String p1) {
	ArrayList<Sunipotent> newProduct = new ArrayList<Sunipotent>();
	ArrayList<Sunipotent> newImmobile = new ArrayList<Sunipotent>();
	DualHashBidiMap<Sunipotent, String> newAssociations = new DualHashBidiMap<Sunipotent, String>();
	for (int i = 0; i < product.size(); i++) {
	    Polynomial arg = get(i).getArgument();
	    Polynomial newArg = arg.old_replace(s1, p1);
	    String associate = stringOf(get(i));
	    Sunipotent replacement = Sunipotent
		    .create(get(i).getRoot(), newArg);
	    newProduct.add(replacement);
	    if (!isMobile(i)) {

		newImmobile.add(replacement);
	    }
	    if (associate != null && associate != s1) {
		newAssociations.put(replacement, associate);
	    }
	    if (associate == s1)
		newAssociations.put(replacement, p1);
	}
	product.removeAll(product);
	product.addAll(newProduct);
	associations = newAssociations;
	immobile.removeAll(immobile);
	immobile.addAll(newImmobile);

    }

    /**
     * Verbose version of equality of Unipotents which documents details of how
     * two Unipotents are not equal when they are not As with Unipotent.equals(
     * Unipotent ) the "equality" condition here is that two Unipotents are
     * equal if their lists of Sunipotent terms are identical. Other fields are
     * ignored, and algebraic identities are not considered.
     * 
     * @param u
     *            to check equality with
     */
    public void equalsVerbose(final Unipotent u) {
	boolean equal = true;
	if (u.getNumberOfTerms() != this.getNumberOfTerms()) {
	    equal = false;
	    System.out.println(u.getNumberOfTerms() + "=/="
		    + this.getNumberOfTerms());
	}
	for (int i = 0; i < Math.max(u.getNumberOfTerms(), this
		.getNumberOfTerms()); i++) {
	    if (i >= u.getNumberOfTerms()) {
		System.out.println("Discrepancy at position " + i);
		equal = false;
		System.out.println(get(i).toString() + "=/= null");
	    } else if (i >= this.getNumberOfTerms()) {
		System.out.println("Discrepancy at position " + i);
		equal = false;
		System.out.println("null =/=" + u.get(i).toString());
	    } else if (!get(i).equals(u.get(i))) {
		System.out.println("Discrepancy at position " + i);
		equal = false;

		if (getArg(i) != u.getArg(i)) {
		    equal = false;
		    System.out.println(getArg(i).toString() + "=/="
			    + u.getArg(i));
		}
		if (!Arrays.equals(get(i).getRoot(), u.get(i).getRoot())) {
		    equal = false;
		    System.out.println(edu.siu.math.egut.io.Algorithms
			    .tupleToString(get(i).getRoot())
			    + "=/="
			    + edu.siu.math.egut.io.Algorithms
				    .tupleToString(get(i).getRoot()));
		}
	    }
	}
	if (equal)
	    System.out.println("Equal.");

    }

    /**
     * If we substitute p1 for s1, and if p1 is a signed variable, i.e. it has
     * only one monomial term, containing only one variable to the first power,
     * with a coefficient which is either 1 or -1, and if s1 is associated to a
     * sunipotent, then we can transfer that association to the new variable.
     * 
     * @param s1
     *            to be substituted
     * @param p1
     *            to substitute; should be a signed variable
     * @throws BadSubstitutionException
     *             if p1 is not a signed variable
     */
    public void substituteSignedVariable(final String s1, final Polynomial p1)
	    throws BadSubstitutionException {
	if (!p1.isASignedVariable())
	    throw new BadSubstitutionException(
		    "attempt to shift association to something other than a signed variable.");
	substitute(s1, p1);
    }

    /**
     * @return an int[][] whose rows are the roots of the sunipotent terms, in
     *         order
     */
    public int[][] getRoots() {
	final int[][] answer = new int[getNumberOfTerms()][group.getRank()];
	for (int i = 0; i < getNumberOfTerms(); i++)
	    answer[i] = get(i).getRoot();
	return answer;
    }

    /**
     * @return a Set containing all string variables that appear in this
     *         unipotent
     */
    public Set<String> getAllVariables() {
	final Set<String> ans = new TreeSet<String>();
	for (final Sunipotent s : product)
	    ans.addAll(s.getArgument().getAllVariables());
	return ans;
    }

    /**
     * @param x
     *            to be split into a prefix and root, such as u_{0100}
     * @return a PrefixRootPair, such as ("u", {0,1,0,0}).
     */
    public static PrefixRootPair prefixRootPair(final String x) {

	String[] pair = x.split("_\\{");

	if (pair.length != 2) {
	    return null;
	}

	if (pair[1].indexOf("}") != pair[1].length() - 1) {
	    return null;
	}
	String tupleString = pair[1].substring(0, pair[1].length() - 1);

	if (!Pattern.compile("\\-?\\d*").matcher(tupleString).matches()) {
	    return null;
	}
	int[] root = edu.siu.math.egut.io.Algorithms
		.tupleFromString(tupleString);
	return new PrefixRootPair(pair[0], root);
    }

    /**
     * State the number of associations. This method exists for debugging
     * purposes.
     */
    public void stateNumberOfAssociations() {
	System.out.println(associations.size() + "associations.");

    }

    /**
     * @return the map of associations between variables and terms
     */
    public BidiMap<Sunipotent, String> getAssociations() {
	return associations;
    }

}
